package hsah;

/**
 * @author shkstart
 * 基于拉链法实现的哈希表
 * key 和 value都存储整型
 * @create 2022-11-05-18:00
 */
public class HashMapByLink {

    private class Node{
//        冲突时使用单链表链接冲突节点
        int key;
        int val;
        Node next;

        public Node(int key, int val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

//    实际存储的元素个数
    private int size;
//    取模数
    private int M;
//    默认哈希表的长度
    private static final int DEFAULT_CAPACITY = 16;
//    默认的负载因子
    private static final double LOAD_FACTOR = 0.75;
//    实际存储Node的数组
    private Node[] table;
    public HashMapByLink(){
        this(DEFAULT_CAPACITY);
    };
    public HashMapByLink(int initcap){
        this.table = new Node[initcap];
        this.M = initcap;

    }

//    对hash进行取模
    private int hash(int key){
//        求绝对值
        return (key & 0x7fffffff) % this.M;
    }

//    若没有重复元素，返回value,若key已经存在，则更新为value,返回之前的value
    public int put(int key,int value){
//        先计算出key的hash值
        int index = hash(key);
//        判断当前哈希表中是否已经存在了这个key,若存在，更新为新的value,返回旧的value
//        table[index]就是链表的头节点
        for (Node x = table[index];x!=null;x= x.next) {
            if(x.key==key){
//                此时哈希表中已经包含了Key,更新为新的value,返回旧的value
                int oldVal = x.val;
                x.val = value;
                return oldVal;
            }
        }

//        此时key不存在，新建一个节点头插相对应的链表头节点   table[Index]
        Node newNode= new Node(key,value);
        Node head = table[index];
//        更新原先头结点的指向为当前节点
        newNode.next=head;
        head = newNode;
        table[index] = newNode;

        size++;
        if(size>LOAD_FACTOR*table.length){
            resize();
        }

        return value;
    }


//    扩容操作，默认将哈希表长度变为2倍
    private void resize() {
        Node[] newTable = new Node[table.length*2];
        this.M =newTable.length;
//        遍历哈希表
        for (int i = 0; i < table.length; i++) {
//            取出连边节点，映射到新的哈希表中
            Node next=null;
            for(Node cur = table[i];cur!=null;cur=next){
                next = cur.next;
                int newIndex = hash(cur.key);
//                头插新哈希表
                cur.next = newTable[newIndex];
                newTable[newIndex]=cur;
            }
        }
        this.table = newTable;
    }

    //    根据key值找到相对应的val
    public int get(int key){
//        求出当前对应key的索引
        int index = hash(key);
        for (Node x = table[index];  x!=null ; x=x.next) {
            if(x.key==key){
                return x.val;
            }
        }
//        此时Keybu存在

        return -1;

    }

//    删除键值对
    public boolean remove(int key,int val){
        int index = hash(key);
//        先判断头结点的情况
        if(table[index].key==key){
            if (table[index].val == val) {
//                此时头节点就是要删除的节点
                Node head = table[index];
                table[index]= table[index].next;
                //这里删除的是头节点的next
                head.next=null;
                size--;
                return true;

            }
        }
//        头节点不是待删除的节点
        Node prev= table[index];
        while (prev.next != null) {
            if(prev.next.key==key){
                if (prev.next.val == val) {
//                    prev节点是待删除节点的前驱节点
                    Node need = prev.next;
                    prev.next = need.next;
                    need.next=null;
                    size--;
                    return true;
                }
            }
            prev = prev.next;



        }
        return false;

    }

}
